package com.future;

/**
 * Description: 最小花费爬楼梯
 *
 * @author weiruibai.vendor
 * Date: 2022/7/28 15:29
 */
public class Solution_BM64 {


    public static void main(String[] args) {
        int[] cost = new int[]{1, 100, 1, 1, 1, 90, 1, 1, 80, 1};
        cost = new int[]{2, 5, 20};
        Solution_BM64 bm64 = new Solution_BM64();
        System.out.println(bm64.minCostClimbingStairs_dp(cost));
        System.out.println("===========");
        System.out.println(bm64.minCostClimbingStairs(cost));
    }

    /**
     * step 1：可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果。
     * step 2：（初始状态） 因为可以直接从第0级或是第1级台阶开始，因此这两级的花费都直接为0.
     * step 3：（状态转移） 每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，
     *  因为在前面的台阶花费我们都得到了，因此每次更新最小值即可，转移方程为：dp[i]=min
     * (dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])。
     *
     * @param cost
     * @return
     */
    public int minCostClimbingStairs_dp(int[] cost) {
        if (cost.length < 3) {
            return 1;
        }
        int N = cost.length;
        int[] dp = new int[N + 1];
        for (int i = 2; i <= N; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[N];
    }


    public int minCostClimbingStairs(int[] cost) {
        if (cost.length < 3) {
            return 1;
        }
        int p1 = process(cost, 0, 0);
        int p2 = process(cost, 1, 0);
        return Math.min(p1, p2);
    }

    /**
     * 0...i，总花费最小
     */
    private int process(int[] cost, int i, int pay) {
        if (i >= cost.length) {
            return pay;
        }
        pay += cost[i];
        if (i == cost.length - 1) {
            return pay;
        }
        // 走一步
        int p1 = process(cost, i + 1, pay);
        // 走2步
        int p2 = process(cost, i + 2, pay);
        return Math.min(p1, p2);
    }
}
